// https://leetcode.cn/problems/powx-n/description/

// 算法思路总结：
// 1. 快速幂算法实现幂函数
// 2. 处理负指数：取倒数，转为正指数计算
// 3. 递归分治：x^n = (x^(n/2))^2，根据n的奇偶性调整
// 4. 使用long long避免整数溢出（INT_MIN取反）
// 5. 时间复杂度：O(logn)，空间复杂度：O(logn)（递归栈）

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    typedef long long ll;
    double myPow(double x, int n)
    {
        ll N = n;
        if (N < 0)
        {
            x = 1.0 / x;
            N = -N;
        }                                           
        return pow(x, N);
    }

    double pow(double x, ll N)
    {
        if (N == 0) return 1.0;

        double tmp = pow(x, N / 2);

        return N & 1 ? tmp * tmp * x : tmp * tmp;
    }
};

int main()
{
    double x1 = 2.00000, x2 = 2.10000;
    int n1 = 10, n2 = 3;

    Solution sol;

    cout << sol.myPow(x1, n1) << endl;
    cout << sol.myPow(x2, n2) << endl;

    return 0;
}